UnivTrevesV1, LNCS, Analysis, bibRecord, 000236

On the Average Sensitivity of Testing Square-Free Numbers

Identifieur interne : 000236 ( LNCS/Analysis ); précédent : 000235; suivant : 000237

On the Average Sensitivity of Testing Square-Free Numbers

Auteurs : Anna Bernasconi [Allemagne] ; Carsten Damm [Allemagne] ; Igor E. Shparlinski [Australie]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 1999.

RBID : ISTEX:C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B

Descripteurs français

Pascal (Inist)
- Circuit combinatoire, Classe complexité, Complexité communication, Fonction booléenne, Informatique théorique.

English descriptors

KwdEn :
- Boolean function, Combinatory circuit, Communication complexity, Complexity class, Computer theory.

Abstract

Abstract: We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain a linear lower bound on the average sensitivity of the Boolean function deciding whether a given integer is square-free. This result allows us to derive a quadratic lower bound for the formula size complexity of testing square-free numbers and a linear lower bound on the average decision tree depth. We also obtain lower bounds on the degrees of exact and approximative polynomial representations of this function.

Url:

https://api.istex.fr/document/C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B/fulltext/pdf

DOI: 10.1007/3-540-48686-0_29

Affiliations:

Links to Exploration step

ISTEX:C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Average Sensitivity of Testing Square-Free Numbers</title>
<author><name sortKey="Bernasconi, Anna" sort="Bernasconi, Anna" uniqKey="Bernasconi A" first="Anna" last="Bernasconi">Anna Bernasconi</name>
</author>
<author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
</author>
<author><name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B</idno>
<date when="1999" year="1999">1999</date>
<idno type="doi">10.1007/3-540-48686-0_29</idno>
<idno type="url">https://api.istex.fr/document/C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000977</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000977</idno>
<idno type="wicri:Area/Istex/Curation">000925</idno>
<idno type="wicri:Area/Istex/Checkpoint">000D67</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000D67</idno>
<idno type="wicri:doubleKey">0302-9743:1999:Bernasconi A:on:the:average</idno>
<idno type="wicri:Area/Main/Merge">002471</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:99-0419773</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">001007</idno>
<idno type="wicri:Area/PascalFrancis/Curation">001787</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000D73</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000D73</idno>
<idno type="wicri:doubleKey">0302-9743:1999:Bernasconi A:on:the:average</idno>
<idno type="wicri:Area/Main/Merge">002525</idno>
<idno type="wicri:Area/Main/Curation">002117</idno>
<idno type="wicri:Area/Main/Exploration">002117</idno>
<idno type="wicri:Area/LNCS/Extraction">000236</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the Average Sensitivity of Testing Square-Free Numbers</title>
<author><name sortKey="Bernasconi, Anna" sort="Bernasconi, Anna" uniqKey="Bernasconi A" first="Anna" last="Bernasconi">Anna Bernasconi</name>
<affiliation wicri:level="4"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Institut für Informatik, Technische Universität München, D-80290, München</wicri:regionArea>
<placeName><settlement type="city">Munich</settlement>
<region type="land" nuts="1">Bavière</region>
<region type="district" nuts="2">District de Haute-Bavière</region>
</placeName>
<orgName type="university">Université technique de Munich</orgName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich für Informatik, Universität Trier, D-54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>School of MPCE, Macquarie University, 2109, Sydney, NSW</wicri:regionArea>
<wicri:noRegion>NSW</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>1999</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B</idno>
<idno type="DOI">10.1007/3-540-48686-0_29</idno>
<idno type="ChapterID">29</idno>
<idno type="ChapterID">Chap29</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Boolean function</term>
<term>Combinatory circuit</term>
<term>Communication complexity</term>
<term>Complexity class</term>
<term>Computer theory</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Circuit combinatoire</term>
<term>Classe complexité</term>
<term>Complexité communication</term>
<term>Fonction booléenne</term>
<term>Informatique théorique</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain a linear lower bound on the average sensitivity of the Boolean function deciding whether a given integer is square-free. This result allows us to derive a quadratic lower bound for the formula size complexity of testing square-free numbers and a linear lower bound on the average decision tree depth. We also obtain lower bounds on the degrees of exact and approximative polynomial representations of this function.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>Australie</li>
</country>
<region><li>Bavière</li>
<li>District de Haute-Bavière</li>
</region>
<settlement><li>Munich</li>
</settlement>
<orgName><li>Université technique de Munich</li>
</orgName>
</list>
<tree><country name="Allemagne"><region name="Bavière"><name sortKey="Bernasconi, Anna" sort="Bernasconi, Anna" uniqKey="Bernasconi A" first="Anna" last="Bernasconi">Anna Bernasconi</name>
</region>
<name sortKey="Bernasconi, Anna" sort="Bernasconi, Anna" uniqKey="Bernasconi A" first="Anna" last="Bernasconi">Anna Bernasconi</name>
<name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
<name sortKey="Damm, Carsten" sort="Damm, Carsten" uniqKey="Damm C" first="Carsten" last="Damm">Carsten Damm</name>
</country>
<country name="Australie"><noRegion><name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
</noRegion>
<name sortKey="Shparlinski, Igor E" sort="Shparlinski, Igor E" uniqKey="Shparlinski I" first="Igor E." last="Shparlinski">Igor E. Shparlinski</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000236 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000236 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    LNCS
   |étape=   Analysis
   |type=    RBID
   |clé=     ISTEX:C780D9D8F11ACEDCE43364AB69ECC4638AB0EF4B
   |texte=   On the Average Sensitivity of Testing Square-Free Numbers
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

Serveur d'exploration sur l'Université de Trèves

On the Average Sensitivity of Testing Square-Free Numbers

On the Average Sensitivity of Testing Square-Free Numbers

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.